void solve()
{
	int n;
	cin >> n;

	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	int M = *max_element(a.begin(), a.end());
	vector<Z> f(M + 1);
	vector<vector<int>> fac(M + 1);
  auto phi = get_eular_phi(M);
	for (int i = 1; i <= M; i++) {
		for (int j = i; j <= M; j += i) {
			fac[j].emplace_back(i);
		}
	}

	Z ans = 0, pw = 1;
	for (int i = 0; i < n; i++) {
		ans *= 2;
		for (auto &d : fac[a[i]]) {
			ans += f[d] * phi[d];
			f[d] += pw;
		}
		pw *= 2;
		cout << ans << '\n';
	}
}